#include<iostream>
#include<vector>
using namespace std;
/*
分隔等和子集
给你一个只包含正整数的非空数组nums 。
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
该题目能够转化为动态规划的思路去解决，但是与传统的0-1背包问题不一样，传统的0-1背包问题是物品不重复装入背包使得不超过
背包总容量的价值最大，改题目相当于是去求能不能使得物品装入背包的大小正好等于所有数相加的一半
dp数组代表的含义是当背包容量为0时是否存在物品装入背包的大小等于所有数组相加的一半
*/
bool dp(vector<int> nums)
{
    //当nums中的数个数小于两个时一定不能被等分
    if(nums.size()<2)
        return false;
    //当nums中的所有元素相加为奇数时一定不能被等分
    int sum=0;
    for(int i=0;i<nums.size();i++)
    {
        sum+=nums[i];
    }
    if(sum%2==1)
        return false;
    //遍历dp数组
    int target = sum/2;
    vector<bool> dp(target+1);
    //初始化dp数组
    dp[0] = true;
    //先遍历物品个数,在遍历背包容量
    for(int i=0;i<nums.size();i++)
    {
        for(int j=target;j<=nums[i];i++)
        {
            dp[j] = dp[j]|dp[j-nums[i]];
        }
    }
    return dp[target];    
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    cout<<dp(nums);
    return 0;
}